package algo.A03_递归和算法复杂度;

/**
 * 获取斐波拉契数列第n项的值
 */
public class T05_斐波那契数列 {
    public static void main(String[] args) {
        int result = solution(8);
        System.out.println("result = " + result);
    }

    /**
     * 时间复杂度：O(2^n)，非常慢
     * T(n) = 2T(n-1) + O(1)
     */
    private static int solution(int n){
        if (n == 2 || n == 1){
            return 1;
        }
        return solution(n-1) + solution(n-2);
    }
}
